package 数据结构和算法.剑指offer.链表.合并两个排序的链表;

import 工具.动态链表生成.DynamicListUtil;
import 工具.单向节点.Node;
import 工具.打印.PrintUtil;

/**
 * 合并两个排序的链表
 * <p>
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的
 * <p>
 * 使用双指针可以解决。使用一个节点prehead作为新的链表的头节点，
 * 然后prev作为遍历的当前节点指针。直接比较第一个和第二个表的值，
 * 把较小的放到新的链表中，最后判断哪个剩下了，将剩下的节点全部放到新的链表中
 */
public class Test {
    public static void main(String[] args) {
        int[] array1 = {1, 2, 3, 4, 5, 6, 7};
        int[] array2 = {3, 4, 5, 7, 8, 9};
        Node head = mergeTwoList(DynamicListUtil.createDynamicList(array1), DynamicListUtil.createDynamicList(array2));
        PrintUtil.println(head.getValue());
    }

    public static Node mergeTwoList(Node head1, Node head2) {
        Node newHead = new Node(-1);
        Node preTemp = newHead;

        while (head1 != null && head2 != null) {
            if (head1.getValue() <= head2.getValue()) {
                preTemp.setNext(head1);
                head1 = head1.getNext();
            } else {
                preTemp.setNext(head2);
                head2 = head2.getNext();
            }

            preTemp = preTemp.getNext();
        }

        if (head1 == null) {
            preTemp.setNext(head2);
        } else {
            preTemp.setNext(head1);
        }

        return newHead.getNext();
    }
}
